package xyf.p09.bfs_dfs;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * ClassName: M1619_PondSizes
 * Description:
 * Author: xyf
 * Date: 9/9/22 9:24 AM
 * Version: 1.0
 **/
public class M1619_PondSizes
{
    public int[] pondSizes(int[][] land)
    {
        List<Integer> result = new ArrayList<>();
        boolean[][] visited = new boolean[land.length][land[0].length];
        for (int i = 0; i < land.length; i++)
        {
            for (int j = 0; j < land[0].length; j++)
            {
                int tmp = dfs(land, i, j, visited);
                if (tmp > 0)
                {
                    result.add(tmp);
                }
            }
        }
        int[] res = result.stream().mapToInt(Integer::valueOf).toArray();
        Arrays.sort(res);
        return res;
    }

    public int dfs(int[][] land, int row, int col, boolean[][] visited)
    {
        if (row < 0 || col < 0 || row > land.length - 1 || col > land[0].length - 1 || visited[row][col])
        {
            return 0;
        }
        if (land[row][col] != 0)
        {
            return 0;
        }

        visited[row][col] = true;
        return 1 + dfs(land, row - 1, col, visited)
                + dfs(land, row + 1, col, visited)
                + dfs(land, row, col - 1, visited)
                + dfs(land, row, col + 1, visited)
                + dfs(land, row - 1, col - 1, visited)
                + dfs(land, row - 1, col + 1, visited)
                + dfs(land, row + 1, col - 1, visited)
                + dfs(land, row + 1, col + 1, visited);
    }
}
